#include <iostream>

void Swap(int &a, int &b){
   int temp = a;
   a = b;
   b = temp;
}

//low:数组的左边界值，开始为0
//high:数组的右边界值，开始为length-1
void QuikSort(int arr[], int low, int high){
    if(low>=high){    //递归退出条件：只有一个元素时
        return;
    }


    int pivot = arr[low];
    int i=low;
    printf("\nlow:%d hign:%d pivot:%d\n", low, high, pivot);
    for (int k = 0; k < 10; ++k)
    {
        printf(" %d ", arr[k]);
    }
    for(int j=low+1;j<=high;j++){
        if(arr[j]<=pivot){        //a[j] is smaller than pivot
            i++;    //a[i] is bigger than pivot
            if(i!=j){
                Swap(arr[i],arr[j]);
            }
        }
    }
    Swap(arr[low],arr[i]);    //Swap pivot to middle position
    printf("\nlow:%d hign:%d \n", low, high);
    for (int k = 0; k < 10; ++k)
    {
        printf(" %d ", arr[k]);
    }
        //进行分化(partition),递归
    QuikSort(arr,low,i-1);        //a[i] is the pivot now
    QuikSort(arr,i+1,high);
}

void QuikSort(int arr[], int length){

    QuikSort(arr,0,length-1);    

}


int main(int argc, char const *argv[])
{
    const int size = 10;
    int arr[size]={0};

    printf("%s\n", "origin:");
    for (int i = 0; i < size; ++i)
    {
        arr[i] = rand() % 100;
        printf(" %d ", arr[i]);
    }

    QuikSort(arr, size);

    printf("\n%s\n", "sorted:");
    for (int i = 0; i < size; ++i)
    {
        printf(" %d ", arr[i]);
    }

    printf("\n");

    return 0;
}